package com.mdnote.algorithm;

import sun.plugin2.applet.Applet2Status;

import java.awt.*;
import java.security.cert.PolicyNode;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/9/12
 * @description 马踏棋盘
 */
public class HorseChessboard {

    private int[][] chessboard;

    private boolean[] isVisited;

    private int size;

    private boolean isFinish;

    public HorseChessboard(int size) {
        this.chessboard = new int[size][size];
        this.isVisited = new boolean[size * size];
        this.size = size;
    }

    public static void main(String[] args) {
        HorseChessboard horseChessboard = new HorseChessboard(6);
        int column = 2;
        int row = 2;
        horseChessboard.chessboard[column][row] = 1;
        horseChessboard.isVisited[column * horseChessboard.size + row] = true;
        horseChessboard.go(column, row, 1);
        for (int i = 0; i < horseChessboard.chessboard.length; i++) {
            for (int j = 0; j < horseChessboard.chessboard[0].length; j++) {
                System.out.printf("%d\t", horseChessboard.chessboard[i][j]);
            }
            System.out.println();
        }
    }

    /**
     * 开始行为
     */
    private void go(int column, int row, int  step) {
        // 先获取到马儿可以走的所有位置
        List<Point> pointList = next(column, row);
        // 优化
        sort(pointList);
        this.chessboard[column][row] = step;
        this.isVisited[column * size + row] = true;
        while (!pointList.isEmpty()) {
            // 取出一个点
            Point point= pointList.remove(0);
            // 将该点标记为已走过
            if (!isVisited[point.x * size + point.y]) {
                go(point.x, point.y, step + 1);
            }
        }
        // 如果还没有完成
        if (step < size * size && !isFinish) {
            // 重置
            this.chessboard[column][row] = 0;
            this.isVisited[column * size + row] = false;
        } else {
            this.isFinish = true;
        }
    }

    /**
     * 获取下一步可以行走的位置列表
     * @param column 行
     * @param row 列
     * @return 列表
     */
    private List<Point> next(int column, int row) {
        // 列是x，行是y
        List<Point> pointList = new ArrayList<>();
        Point point = new Point();
        // 马儿可以走8个位置
        if ((point.x = column + 2) < size && (point.y = row + 1) < size) {
            pointList.add(new Point(point));
        }
        if ((point.x = column + 1) < size && (point.y = row + 2) < size) {
            pointList.add(new Point(point));
        }
        if ((point.x = column - 1) >= 0 && (point.y = row + 2) < size) {
            pointList.add(new Point(point));
        }
        if ((point.x = column - 2) >= 0 && (point.y = row + 1) < size) {
            pointList.add(new Point(point));
        }
        if ((point.x = column - 2) >= 0 && (point.y = row - 1) >= 0) {
            pointList.add(new Point(point));
        }
        if ((point.x = column - 1) >= 0 && (point.y = row - 2) >= 0) {
            pointList.add(new Point(point));
        }
        if ((point.x = column + 1) < size && (point.y = row - 2) >= 0) {
            pointList.add(new Point(point));
        }
        if ((point.x = column + 2) < size && (point.y = row - 1) >= 0) {
            pointList.add(new Point(point));
        }
        return pointList;
    }

    /**
     * 优化，对pointList进行排序，让下一次递归次数少的元素在前面
     */
    private void sort(List<Point> pointList) {
        pointList.sort(new Comparator<Point>() {
            @Override
            public int compare(Point p1, Point p2) {
                int p1Size = next(p1.x, p1.y).size();
                int p2Size = next(p2.x, p2.y).size();
                if (p1Size > p2Size) {
                    // 返回正数，o1放在后面
                    return 1;
                } else if (p1Size < p2Size) {
                    return -1;
                } else {
                    return 0;
                }
            }
        });

    }
}
